import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;


public class Leetcode373 {
    public static void main(String[] args) {
        System.out.println(kSmallestPairs(new int[]{1, 1, 2}, new int[]{1, 2, 3}, 33));
    }

    static {
        System.gc();
        System.runFinalization();
    }

    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2) -> nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]]);

        int minNumber = Math.min(k, nums1.length);

        for (int i = 0; i < minNumber; i++) {
            pq.add(new int[]{i, 0});
        }

        int num2Length = nums2.length;
        List<List<Integer>> res = new ArrayList<>();
        while (k > 0 && !pq.isEmpty()) {
            int[] min = pq.poll();
            res.add(List.of(nums1[min[0]], nums2[min[1]]));

            if (min[1] + 1 < num2Length) {
                pq.add(new int[]{min[0], min[1] + 1});
            }

            k--;
        }

        return res;
    }
}
